package offer;

/**
 * @Author Elephas
 * @Date 2022/1/21
 **/
public class MaxPathSum {
    /*
        把树看作是逻辑上的无向图，但其底层实现是有向图，需要在这种情况下找出最大路径
     */
     /*
        把树看作是逻辑上的无向图，但其底层实现是有向图，需要在这种情况下找出最大路径,从叶子向根进行累加
     */
    static int maxSum;
    public int maxPathSum(TreeNode root){
        if(root == null){
            return 0;
        }
        maxSum = root.val;
        maxPathSumHelper(root);
        return maxSum;
    }
    /*
        从叶子向根进行累加
     */
    public int maxPathSumHelper(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = maxPathSumHelper(root.left);
        int right = maxPathSumHelper(root.right);
        int curSum = left + root.val;
        int rootLeft = root.val + left;
        int rootRight = root.val +right;
        int rootLeftRight = rootRight + left;
        int curMax;
        // 寻找root,rootLeft,rootRight中最大值
        if(root.val > rootLeft && root.val > rootLeftRight && root.val > rootRight){
            curMax = root.val;
        }else if(rootLeftRight >= rootLeft && rootLeftRight >= rootRight){
            curMax = rootLeftRight;
        }else if(rootLeft >= rootRight){
            curMax = rootLeft;
        }else{
            curMax = rootRight;
        }
        maxSum = curMax > maxSum? curMax : maxSum;
        /*
            把较长的子树返回，由题意，左子树和右子树只能返回一个，或者直接返回根节点
         */
        if(root.val > rootLeft && root.val > rootRight){
            curMax = root.val;
        }else if(rootLeft >= rootRight){
            curMax = rootLeft;
        }else{
            curMax = rootRight;
        }
        return curMax;
    }

}
